#include <bits/stdc++.h>
#include "Utils.hpp"
#include "QuickSort.hpp"

class Sort
{
private:
    static int Partion(std::vector<int>& nums, int leftBound, int rightBound)
    {
        int left = leftBound;
        int right = rightBound - 1;
        int pivot = nums[rightBound];
        while (left <= right)
        {
            while (left <= right && nums[left] <= pivot) left++;
            while (left <= right && nums[right] > pivot) right--;
            if (left < right) std::swap(nums[left], nums[right]);
        }
        std::swap(nums[left], nums[rightBound]);
        // Print(nums);
        return left;
    }
public:
    static void SelectSort(std::vector<int>& nums)
    {
        for (size_t i = 0; i < nums.size() - 1; i++)
        {
            size_t minPos = i;
            for (size_t j = i + 1; j < nums.size(); j++)
            {
                if (nums[j] < nums[minPos]) minPos = j;
            }
            std::swap(nums[minPos], nums[i]);
        }
    }

    static void BubbleSort(std::vector<int>& nums)
    {
        for (size_t i = nums.size() - 1; i > 0; i--)
        {
            for (size_t j = 0; j < i; j++)
                if (nums[j] > nums[j+1]) std::swap(nums[j], nums[j+1]);
        }
    }

    static void InsertSort(std::vector<int>& nums)
    {
        for (size_t i = 1; i < nums.size(); i++)
        {
            for (size_t j = i; j > 0; j--)
            {
                if (nums[j] < nums[j-1]) std::swap(nums[j], nums[j-1]);
            }
            
        }
    }

    static void ShellSort(std::vector<int>& nums)
    {
        int H = 1;
        while (H <= nums.size()/3)
        {
            H = H * 3 + 1;
        }
        
        for (size_t h = H; h > 0; h = (h - 1)/3)
        {
            for (size_t i = h; i < nums.size(); i++)
            {
                for (size_t j = i; j > h-1; j-=h)
                {
                    if (nums[j] < nums[j-h]) std::swap(nums[j], nums[j-h]);
                }
            }
        }
    }

    static void QuickSort(std::vector<int>& nums, int leftBound, int rightBound)
    {
        if (leftBound >= rightBound) return;
        int mid = Partion(nums, leftBound, rightBound);
        QuickSort(nums, leftBound, mid-1);
        QuickSort(nums, mid+1, rightBound);
    }

    // 思考:给对象计数排序如何排序
    static void CountSort(std::vector<int>& nums)
    {
        std::vector<int> count = {0,0,0,0,0,0,0,0,0,0};
        for (size_t i = 0; i < nums.size(); i++)
        {
            count[nums[i]]++;
        }
        // Print(nums);
        // Print(count);
        for (size_t i = 1; i < count.size(); i++)
        {
            count[i] = count[i] + count[i-1];
        }
        // Print(count);
        
        std::vector<int> temp(nums.size(), -1);
        // Print(temp);
        // Print(nums);
        for (int i = nums.size()-1; i >= 0; i--)
        {
            temp[--count[nums[i]]] = nums[i];
        }
        nums = temp;
    }

    static void RadixSort(std::vector<int>& nums)
    {
        for (size_t k = 0; k < 4; k++)
        {
            int div = std::pow(10, k);
            std::vector<int> count = {0,0,0,0,0,0,0,0,0,0};
            for (size_t i = 0; i < nums.size(); i++)
            {
                int num = nums[i] / div % 10;
                count[num]++;
            }
            for (size_t i = 1; i < count.size(); i++)
            {
                count[i] = count[i] + count[i-1];
            }
            std::vector<int> temp(nums.size(), -1);
            for (int i = nums.size()-1; i >= 0; i--)
            {
                int div = std::pow(10, k);
                int num = nums[i] / div % 10;
                temp[--count[num]] = nums[i];
            }
            nums = temp;
        }
    }

    static void Print(const std::vector<int>& nums)
    {
        for (size_t i = 0; i < nums.size(); i++)
        {
            std::cout << nums[i] << " ";
        }
        std::cout << std::endl;
        
    }

    static bool TestSort()
    {
        for (size_t i = 0; i < 10000; i++)
        {
            std::vector<int> nums;
            Utils::GenRandNums(nums, 0, 9, 100, time(NULL)+i);
            std::vector<int> sortedNums = nums;
            Sort::CountSort(sortedNums);
            if (!Utils::Check(nums, sortedNums))
            {
                return false;
            }
        }
        return true;
    }

    static bool TestRadixSort()
    {
        for (size_t i = 0; i < 10000; i++)
        {
            std::vector<int> nums;
            Utils::GenRandNums(nums, 0, 9999, 100, time(NULL)+i);
            std::vector<int> sortedNums = nums;
            Sort::RadixSort(sortedNums);
            if (!Utils::Check(nums, sortedNums))
            {
                return false;
            }
        }
        return true;
    }
};

int main() 
{
    if (!Sort::TestRadixSort())
    {
        return 0;
    }
    std::cout << "right" << std::endl;
}
